package algorithm.mashibing;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Random;

public class SortTest {

	public static void main(String[] args) throws Exception {
		test(10000, 10000, 20, "quick");
	}

//************************************************************************************************************
	// ��������
	public static void quick(int[] arr) {
		quickSort(arr, 0, arr.length - 1);
	}

	private static void quickSort(int[] arr, int leftBound, int rightBound) {
		if (leftBound >= rightBound)
			return;
		int mid = one(arr, leftBound, rightBound);
		quickSort(arr, leftBound, mid - 1);
		quickSort(arr, mid + 1, rightBound);
	}

	private static int one(int[] arr, int leftBound, int rightBound) {
		int pivot = arr[rightBound];
		int left = leftBound, right = rightBound - 1;
		while (left <= right) {
			while (left <= right && arr[left] <= pivot)
				left++;
			while (left <= right && arr[right] > pivot)
				right--;
			if (left <= right)
				swap(left, right, arr);
		}
		swap(left, rightBound, arr);
		return left;
	}

	// �鲢����
	public static void merge(int[] arr) {
		int n = arr.length, mid = n / 2, i = 0, j = mid + 1, k = 0;
		int[] temp = new int[n];
		while (i <= mid && j < n)
			temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
		while (i <= mid)
			temp[k++] = arr[i++];
		while (j < n)
			temp[k++] = arr[j++];
		printArr(temp);
	}

	// ϣ������
	public static void shell(int[] arr) {
		int h = 1, n = arr.length;
		while (h <= n)
			h = h * 3 + 1;
		while ((h = (h - 1) / 3) > 0)
			for (int i = h; i < n; i++)
				for (int j = i; j > h - 1 && arr[j] < arr[j - h]; j -= h)
					swap(j, j - h, arr);
	}

	// ϣ���������
	public static void shellSort(int[] a) {
		int n = a.length;
		int d = n / 2;
		while (d > 0) {
			for (int i = d; i < n; i++) {
				int j = i - d;
				while (j >= 0 && a[j] > a[j + d]) {
					int tmp = a[j];
					a[j] = a[j + d];
					a[j + d] = tmp;
					j = j - d;
				}
			}
			d = d / 2;
		}
	}

	// ��������
	public static void insert(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int temp = arr[i];
			for (int j = i - 1; j >= 0 && temp < arr[j]; j--)
				if (j < 1 || temp >= arr[j - 1]) {
					for (int k = i; k > j; k--)
						arr[k] = arr[k - 1];
					arr[j] = temp;
					break;
				}
		}
	}

	// ѡ������
	public static void select(int[] arr) {
		for (int i = arr.length - 1; i > 0; i--) {
			int index = i;
			for (int j = 0; j < i; j++)
				if (arr[j] > arr[index])
					index = j;
			swap(i, index, arr);
		}
	}

	// ð������
	public static void bubble(int[] arr) {
		for (int i = arr.length - 1; i > 0; i--)
			for (int j = 0; j < i; j++)
				if (arr[j] > arr[j + 1])
					swap(j, j + 1, arr);
	}

//************************************************************************************************************
	public static void test(int length, int max, int num, String method) throws Exception {
		long[] time = new long[num];
		long all = 0;
		boolean allIs = true;
		Method method2 = Class.forName("mashibing.SortTest").getMethod(method, int[].class);
		for (int i = 0; i < num; i++) {
			int[] arr1 = createArr(length, max);
			int[] arr2 = copyArr(arr1);
			long time1 = System.currentTimeMillis();
			Arrays.sort(arr1);
			long time2 = System.currentTimeMillis();
			method2.invoke(null, arr2);
			long time3 = System.currentTimeMillis();
			time[i] = time3 + time1 - 2 * time2;
			all += time[i];
			boolean is = check(arr1, arr2);
			if (!is) {
				System.out.println(is);
				return;
			}
			System.out.print(is + "," + time[i] + "ms  ");
		}
		System.out.println(
				"\nmethod \"" + method + "\" is " + allIs + (allIs ? " , avg extra time = " + all / num + "ms" : ""));
	}

	public static int[] createArr(int length, int max) {
		int[] arr = new int[length];
		Random r = new Random();
		for (int i = 0; i < length; i++)
			arr[i] = r.nextInt(max);
		return arr;
	}

	private static int[] copyArr(int[] arr) {
		int[] newArr = new int[arr.length];
		for (int i = 0; i < arr.length; i++)
			newArr[i] = arr[i];
		return newArr;
	}

	public static void printArr(int[] arr) {
		System.out.print("[" + arr[0]);
		for (int i = 1; i < arr.length; i++)
			System.out.print("," + arr[i]);
		System.out.println("]");
	}

	public static boolean check(int[] arr1, int[] arr2) {
		for (int i = 0; i < arr1.length; i++)
			if (arr1[i] != arr2[i])
				return false;
		return true;
	}

	public static void swap(int x, int y, int[] arr) {
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
}
